Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2015
Conference article
Open Access
Behavioral entropy and profitability in retail
Guidotti R., Coscia M., Pedreschi D., Pennacchioli D.
Human behavior is predictable in principle: people are systematic in their everyday choices. This predictability can be used to plan events and infrastructure, both for the public good and for private gains. In this paper we investigate the largely unexplored relationship between the systematic behavior of a customer and its profitability for a retail company. We estimate a customer's behavioral entropy over two dimensions: the basket entropy is the variety of what customers buy, and the spatio-temporal entropy is the spatial and temporal variety of their shopping sessions. To estimate the basket and the spatiotemporal entropy we use data mining and information theoretic techniques. We find that predictable systematic customers are more profitable for a supermarket: their average per capita expenditures are higher than non systematic customers and they visit the shops more often. However, this higher individual profitability is masked by its overall level. The highly systematic customers are a minority of the customer set. As a consequence, the total amount of revenues they generate is small. We suggest that favoring a systematic behavior in their customers might be a good strategy for supermarkets to increase revenue. These results are based on data coming from a large Italian supermarket chain, including more than 50 thousand customers visiting 23 shops to purchase more than 80 thousand distinct products.Source: IEEE International Conference on Data Science and Advanced Analytics, Paris, France, 19-21/10/2015
DOI: 10.1109/dsaa.2015.7344821
Project(s): CIMPLEX
, SoBigData
Metrics:
Guidotti R., Coscia M., Pedreschi D., Pennacchioli D.
Human behavior is predictable in principle: people are systematic in their everyday choices. This predictability can be used to plan events and infrastructure, both for the public good and for private gains. In this paper we investigate the largely unexplored relationship between the systematic behavior of a customer and its profitability for a retail company. We estimate a customer's behavioral entropy over two dimensions: the basket entropy is the variety of what customers buy, and the spatio-temporal entropy is the spatial and temporal variety of their shopping sessions. To estimate the basket and the spatiotemporal entropy we use data mining and information theoretic techniques. We find that predictable systematic customers are more profitable for a supermarket: their average per capita expenditures are higher than non systematic customers and they visit the shops more often. However, this higher individual profitability is masked by its overall level. The highly systematic customers are a minority of the customer set. As a consequence, the total amount of revenues they generate is small. We suggest that favoring a systematic behavior in their customers might be a good strategy for supermarkets to increase revenue. These results are based on data coming from a large Italian supermarket chain, including more than 50 thousand customers visiting 23 shops to purchase more than 80 thousand distinct products.Source: IEEE International Conference on Data Science and Advanced Analytics, Paris, France, 19-21/10/2015
DOI: 10.1109/dsaa.2015.7344821
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
www.michelecoscia.com 
| doi.org 
| ieeexplore.ieee.org | CNR ExploRA
2014
Journal article
Open Access
The retail market as a complex system
Pennacchioli D., Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
Aim of this paper is to introduce the complex system perspective into retail market analysis. Currently, to understand the retail market means to search for local patterns at the micro level, involving the segmentation, separation and profiling of diverse groups of consumers. In other contexts, however, markets are modelled as complex systems. Such strategy is able to uncover emerging regularities and patterns that make markets more predictable, e.g. enabling to predict how much a country's GDP will grow. Rather than isolate actors in homogeneous groups, this strategy requires to consider the system as a whole, as the emerging pattern can be detected only as a result of the interaction between its self-organizing parts. This assumption holds also in the retail market: each customer can be seen as an independent unit maximizing its own utility function. As a consequence, the global behaviour of the retail market naturally emerges, enabling a novel description of its properties, complementary to the local pattern approach. Such task demands for a data-driven empirical framework. In this paper, we analyse a unique transaction database, recording the micro-purchases of a million customers observed for several years in the stores of a national supermarket chain. We show the emergence of the fundamental pattern of this complex system, connecting the products' volumes of sales with the customers' volumes of purchases. This pattern has a number of applications. We provide three of them. By enabling us to evaluate the sophistication of needs that a customer has and a product satisfies, this pattern has been applied to the task of uncovering the hierarchy of needs of the customers, providing a hint about what is the next product a customer could be interested in buying and predicting in which shop she is likely to go to buy it.Source: EPJ 3 (2014). doi:10.1140/epjds/s13688-014-0033-x
DOI: 10.1140/epjds/s13688-014-0033-x
Project(s): DATA SIM
Metrics:
Pennacchioli D., Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
Aim of this paper is to introduce the complex system perspective into retail market analysis. Currently, to understand the retail market means to search for local patterns at the micro level, involving the segmentation, separation and profiling of diverse groups of consumers. In other contexts, however, markets are modelled as complex systems. Such strategy is able to uncover emerging regularities and patterns that make markets more predictable, e.g. enabling to predict how much a country's GDP will grow. Rather than isolate actors in homogeneous groups, this strategy requires to consider the system as a whole, as the emerging pattern can be detected only as a result of the interaction between its self-organizing parts. This assumption holds also in the retail market: each customer can be seen as an independent unit maximizing its own utility function. As a consequence, the global behaviour of the retail market naturally emerges, enabling a novel description of its properties, complementary to the local pattern approach. Such task demands for a data-driven empirical framework. In this paper, we analyse a unique transaction database, recording the micro-purchases of a million customers observed for several years in the stores of a national supermarket chain. We show the emergence of the fundamental pattern of this complex system, connecting the products' volumes of sales with the customers' volumes of purchases. This pattern has a number of applications. We provide three of them. By enabling us to evaluate the sophistication of needs that a customer has and a product satisfies, this pattern has been applied to the task of uncovering the hierarchy of needs of the customers, providing a hint about what is the next product a customer could be interested in buying and predicting in which shop she is likely to go to buy it.Source: EPJ 3 (2014). doi:10.1140/epjds/s13688-014-0033-x
DOI: 10.1140/epjds/s13688-014-0033-x
Project(s): DATA SIM
Metrics:
See at:
EPJ Data Science | EPJ Data Science | www.epjdatascience.com | CNR ExploRA
2013
Journal article
Open Access
Evolving networks: eras and turning points
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: Intelligent data analysis 17 (2013): 27–48. doi:10.3233/IDA-120566
DOI: 10.3233/ida-120566
Metrics:
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: Intelligent data analysis 17 (2013): 27–48. doi:10.3233/IDA-120566
DOI: 10.3233/ida-120566
Metrics:
See at:
Intelligent Data Analysis | Intelligent Data Analysis | CNR ExploRA
2013
Journal article
Restricted
Multidimensional networks: foundations of structural analysis
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Complex networks have been receiving increasing attention by the scientific community, thanks also to the increasing availability of real-world network data. So far, network analysis has focused on the characterization and measurement of local and global properties of graphs, such as diameter, degree distribution, centrality, and so on. In the last years, the multidimensional nature of many real world networks has been pointed out, i.e. many networks containing multiple connections between any pair of nodes have been analyzed. Despite the importance of analyzing this kind of networks was recognized by previous works, a complete framework for multidimensional network analysis is still missing. Such a framework would enable the analysts to study different phenomena, that can be either the generalization to the multidimensional setting of what happens in monodimensional networks, or a new class of phenomena induced by the additional degree of complexity that multidimensionality provides in real networks. The aim of this paper is then to give the basis for multidimensional network analysis: we present a solid repertoire of basic concepts and analytical measures, which take into account the general structure of multidimensional networks. We tested our framework on different real world multidimensional networks, showing the validity and the meaningfulness of the measures introduced, that are able to extract important and non-random information about complex phenomena in such networks.Source: World wide web (Bussum) 16 (2013): 567–593. doi:10.1007/s11280-012-0190-4 ?
DOI: 10.1007/s11280-012-0190-4
Metrics:
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Complex networks have been receiving increasing attention by the scientific community, thanks also to the increasing availability of real-world network data. So far, network analysis has focused on the characterization and measurement of local and global properties of graphs, such as diameter, degree distribution, centrality, and so on. In the last years, the multidimensional nature of many real world networks has been pointed out, i.e. many networks containing multiple connections between any pair of nodes have been analyzed. Despite the importance of analyzing this kind of networks was recognized by previous works, a complete framework for multidimensional network analysis is still missing. Such a framework would enable the analysts to study different phenomena, that can be either the generalization to the multidimensional setting of what happens in monodimensional networks, or a new class of phenomena induced by the additional degree of complexity that multidimensionality provides in real networks. The aim of this paper is then to give the basis for multidimensional network analysis: we present a solid repertoire of basic concepts and analytical measures, which take into account the general structure of multidimensional networks. We tested our framework on different real world multidimensional networks, showing the validity and the meaningfulness of the measures introduced, that are able to extract important and non-random information about complex phenomena in such networks.Source: World wide web (Bussum) 16 (2013): 567–593. doi:10.1007/s11280-012-0190-4 ?
DOI: 10.1007/s11280-012-0190-4
Metrics:
See at:
World Wide Web | www.springerlink.com | CNR ExploRA
2012
Report
Open Access
A classification for community discovery methods in complex networks
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges,multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: ISTI Technical reports, pp.512–546, 2012
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges,multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: ISTI Technical reports, pp.512–546, 2012
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
See at:
arXiv.org e-Print Archive | Statistical Analysis and Data Mining The ASA Data Science Journal | ISTI Repository | Statistical Analysis and Data Mining The ASA Data Science Journal | doi.org | CNR ExploRA
2012
Journal article
Restricted
Discovering the geographical borders of human mobility
Rinzivillo S., Mainardi S., Pezzoni F., Coscia M., Pedreschi D., Giannotti F.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human behavior and interactions. Broad, extensive, and multidisciplinary research has been devoted to the extraction of non-trivial knowledge from this novel form of data. We propose a general method to determine the influence of social and mobility behavior over a specific geographical area in order to evaluate to what extent the current administrative borders represent the real basin of human movement. We build a network representation of human movement starting with vehicle GPS tracks and extract relevant clusters, which are then mapped back onto the territory, finding a good match with the existing administrative borders. The novelty of our approach is the focus on a detailed spatial resolution, we map emerging borders in terms of individual municipalities, rather than macro regional or national areas. We present a series of experiments to illustrate and evaluate the effectiveness of our approach.Source: KI. Künstliche Intelligenz (Oldenbourg) 26 (2012): 253–260. doi:10.1007/s13218-012-0181-8
DOI: 10.1007/s13218-012-0181-8
Project(s): DATA SIM
Metrics:
Rinzivillo S., Mainardi S., Pezzoni F., Coscia M., Pedreschi D., Giannotti F.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human behavior and interactions. Broad, extensive, and multidisciplinary research has been devoted to the extraction of non-trivial knowledge from this novel form of data. We propose a general method to determine the influence of social and mobility behavior over a specific geographical area in order to evaluate to what extent the current administrative borders represent the real basin of human movement. We build a network representation of human movement starting with vehicle GPS tracks and extract relevant clusters, which are then mapped back onto the territory, finding a good match with the existing administrative borders. The novelty of our approach is the focus on a detailed spatial resolution, we map emerging borders in terms of individual municipalities, rather than macro regional or national areas. We present a series of experiments to illustrate and evaluate the effectiveness of our approach.Source: KI. Künstliche Intelligenz (Oldenbourg) 26 (2012): 253–260. doi:10.1007/s13218-012-0181-8
DOI: 10.1007/s13218-012-0181-8
Project(s): DATA SIM
Metrics:
See at:
KI - Künstliche Intelligenz | link.springer.com | CNR ExploRA
2012
Report
Open Access
DEMON: a local-first discovery method for overlapping communities
Coscia M., Rossetti G., Giannotti F., Pedreschi D.
Community discovery in complex networks is an interest- ing problem with a number of applications, especially in the knowledge extraction task in social and information net- works. However, many large networks often lack a particular community organization at a global level. In these cases, tra- ditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We pro- pose here a simple local-rst approach to community dis- covery, able to unveil the modular organization of real com- plex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighbor- hood, using a label propagation algorithm; nally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a lim- ited time complexity, so that it can be used on web-scale real networksSource: ISTI Technical reports, 2012
Project(s): DATA SIM
Coscia M., Rossetti G., Giannotti F., Pedreschi D.
Community discovery in complex networks is an interest- ing problem with a number of applications, especially in the knowledge extraction task in social and information net- works. However, many large networks often lack a particular community organization at a global level. In these cases, tra- ditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We pro- pose here a simple local-rst approach to community dis- covery, able to unveil the modular organization of real com- plex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighbor- hood, using a label propagation algorithm; nally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a lim- ited time complexity, so that it can be used on web-scale real networksSource: ISTI Technical reports, 2012
Project(s): DATA SIM
See at:
arxiv.org | ISTI Repository | CNR ExploRA
2012
Conference article
Open Access
Classifying trust/distrust relationships in online social networks
Bachi G., Coscia M., Monreale A., Giannotti F.
Online social networks are increasingly being used as places where communities gather to exchange information, form opinions, collaborate in response to events. An aspect of this information exchange is how to determine if a source of social information can be trusted or not. Data mining literature addresses this problem. However, if usually employs social bal- ance theories, by looking at small structures in complex networks known as triangles. This has proven effective in some cases, but it under performs in the lack of context information about the relation and in more complex interactive structures. In this paper we address the problem of creating a framework for the trust inference, able to infer the trust/distrust relationships in those relational environments that cannot be described by using the classical social balance theory. We do so by decomposing a trust network in its ego network components and mining on this ego network set the trust relationships, extending a well known graph mining algorithm. We test our framework on three public datasets describing trust relationships in the real world (from the social media Epinions, Slashdot and Wikipedia) and confronting our results with the trust inference state of the art, showing better performances where the social balance theory fails.Source: International Conference on Privacy, Security, Risk and Trust 2012 and 2012, pp. 552–557, Amsterdam, 3-5 September 2012
DOI: 10.1109/socialcom-passat.2012.115
Metrics:
Bachi G., Coscia M., Monreale A., Giannotti F.
Online social networks are increasingly being used as places where communities gather to exchange information, form opinions, collaborate in response to events. An aspect of this information exchange is how to determine if a source of social information can be trusted or not. Data mining literature addresses this problem. However, if usually employs social bal- ance theories, by looking at small structures in complex networks known as triangles. This has proven effective in some cases, but it under performs in the lack of context information about the relation and in more complex interactive structures. In this paper we address the problem of creating a framework for the trust inference, able to infer the trust/distrust relationships in those relational environments that cannot be described by using the classical social balance theory. We do so by decomposing a trust network in its ego network components and mining on this ego network set the trust relationships, extending a well known graph mining algorithm. We test our framework on three public datasets describing trust relationships in the real world (from the social media Epinions, Slashdot and Wikipedia) and confronting our results with the trust inference state of the art, showing better performances where the social balance theory fails.Source: International Conference on Privacy, Security, Risk and Trust 2012 and 2012, pp. 552–557, Amsterdam, 3-5 September 2012
DOI: 10.1109/socialcom-passat.2012.115
Metrics:
See at:
www.michelecoscia.com | doi.org | ieeexplore.ieee.org | CNR ExploRA
2012
Conference article
Restricted
Optimal spatial resolution for the analysis of human mobility
Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human be- haviors and interactions. This data availability leads to challenges in the knowledge discovery community. Several different analyses have been performed on the traces of human trajectories, such as understanding the real borders of human mobility or mining social interactions derived from mobility and viceversa. However, the data quality of the digital traces of human mobility has a dramatic impact over the knowledge that it is possible to mine, and this issue has not been thoroughly tackled so far in literature. In this paper, we mine and analyze with complex network techniques a large dataset of human trajectories, a GPS dataset from more than 150k vehicles in Italy. We build a multiresolution grid and we map the trajectories with several complex networks, by connecting the different areas of our region of interest. Then we analyze the structural properties of these networks and the quality of the borders it is possible to infer from them. The result is a significant advancement in our understanding of the data transformation process that is needed to connect mobility with social network analysis and mining.Source: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 248–252, Instanbul, Turkey, 26-29 August 2012
Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human be- haviors and interactions. This data availability leads to challenges in the knowledge discovery community. Several different analyses have been performed on the traces of human trajectories, such as understanding the real borders of human mobility or mining social interactions derived from mobility and viceversa. However, the data quality of the digital traces of human mobility has a dramatic impact over the knowledge that it is possible to mine, and this issue has not been thoroughly tackled so far in literature. In this paper, we mine and analyze with complex network techniques a large dataset of human trajectories, a GPS dataset from more than 150k vehicles in Italy. We build a multiresolution grid and we map the trajectories with several complex networks, by connecting the different areas of our region of interest. Then we analyze the structural properties of these networks and the quality of the borders it is possible to infer from them. The result is a significant advancement in our understanding of the data transformation process that is needed to connect mobility with social network analysis and mining.Source: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 248–252, Instanbul, Turkey, 26-29 August 2012
See at:
ieeexplore.ieee.org | CNR ExploRA
2012
Conference article
Restricted
Knowing where and how criminal organizations operate using web content
Coscia M., Rios V.
We develop a framework that uses Web content to obtain quantitative information about a phenomenon that would otherwise require the operation of large scale, expensive intelligence exercises. Exploiting indexed reliable sources such as online newspapers and blogs, we use unambiguous query terms to characterize a complex evolving phenomena and solve a security policy problem: identifying the areas of operation and modus operandi of criminal organizations, in particular, Mexican drug tracking organizations over the last two decades. We validate our methodology by comparing information that is known with certainty with the one we extracted using our framework.We show that our framework is able to use information available on the web to eciently extract implicit knowledge about criminal organizations. In the scenario of Mexican drug tracking, our ndings provide evidence that criminal organizations are more strategic and operate in more dierentiated ways than current academic literature thought.Source: The 21st ACM International Conference on Information and Knowledge Management, pp. 1412–1421, Maui, Hawaii, USA, October 29-November 2 2012
DOI: 10.1145/2396761.2398446
Metrics:
Coscia M., Rios V.
We develop a framework that uses Web content to obtain quantitative information about a phenomenon that would otherwise require the operation of large scale, expensive intelligence exercises. Exploiting indexed reliable sources such as online newspapers and blogs, we use unambiguous query terms to characterize a complex evolving phenomena and solve a security policy problem: identifying the areas of operation and modus operandi of criminal organizations, in particular, Mexican drug tracking organizations over the last two decades. We validate our methodology by comparing information that is known with certainty with the one we extracted using our framework.We show that our framework is able to use information available on the web to eciently extract implicit knowledge about criminal organizations. In the scenario of Mexican drug tracking, our ndings provide evidence that criminal organizations are more strategic and operate in more dierentiated ways than current academic literature thought.Source: The 21st ACM International Conference on Information and Knowledge Management, pp. 1412–1421, Maui, Hawaii, USA, October 29-November 2 2012
DOI: 10.1145/2396761.2398446
Metrics:
See at:
dl.acm.org | doi.org | CNR ExploRA
2011
Conference article
Open Access
Finding redundant and complementary communities in multidimensional networks
Berlingerio Michele, Coscia Michele, Giannotti Fosca
Community Discovery in networks is the problem of detecting, for each node, its membership to one of more groups of nodes, the communities, that are densely connected, or highly interactive. We de ne this problem for multidimensional networks, i.e. where more than one connection may reside between any two nodes. We introduce two measures able to characterize the communities found. Our experiments on real world data support the methodology proposed, and open the way for a new class of algorithms, aimed at capturing the multifaceted complexity of connections among nodes in a network.Source: 20th ACM international conference on Information and knowledge management, CIKM'11, pp. 2181–2184, Glasgow, UK, 24-28 October 2011
DOI: 10.1145/2063576.2063921
Metrics:
Berlingerio Michele, Coscia Michele, Giannotti Fosca
Community Discovery in networks is the problem of detecting, for each node, its membership to one of more groups of nodes, the communities, that are densely connected, or highly interactive. We de ne this problem for multidimensional networks, i.e. where more than one connection may reside between any two nodes. We introduce two measures able to characterize the communities found. Our experiments on real world data support the methodology proposed, and open the way for a new class of algorithms, aimed at capturing the multifaceted complexity of connections among nodes in a network.Source: 20th ACM international conference on Information and knowledge management, CIKM'11, pp. 2181–2184, Glasgow, UK, 24-28 October 2011
DOI: 10.1145/2063576.2063921
Metrics:
See at:
www.michelecoscia.com | dl.acm.org | doi.org | CNR ExploRA
2011
Journal article
Open Access
The pursuit of hubbiness: analysis of hubs in large multidimensional networks
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Hubs are highly connected nodes within a network. In complex network analysis, hubs have been widely studied, and are at the basis of many tasks, such as web search and epidemic outbreak detection. In reality, networks are often multidimensional, i.e., there can exist multiple connections between any pair of nodes. In this setting, the concept of hub depends on the multiple dimensions of the network, whose interplay becomes crucial for the connectedness of a node. In this paper, we characterize multidimensional hubs. We consider the multidimensional generalization of the degree and introduce a new class of measures, that we call Dimension Relevance, aimed at analyzing the importance of different dimensions for the hubbiness of a node. We assess the meaningfulness of our measures by comparing them on real networks and null models, then we study the interplay among dimensions and their effect on node connectivity. Our findings show that: (i) multidimensional hubs do exist and their characterization yields interesting insights and (ii) it is possible to detect the most influential dimensions that cause the different hub behaviors. We demonstrate the usefulness of multidimensional analysis in three real world domains: detection of ambiguous query terms in a word-word query log network, outlier detection in a social network, and temporal analysis of behaviors in a co-authorship network.Source: Journal of computational science (Print) 2 (2011): 223–237. doi:10.1016/j.jocs.2011.05.009
DOI: 10.1016/j.jocs.2011.05.009
Metrics:
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Hubs are highly connected nodes within a network. In complex network analysis, hubs have been widely studied, and are at the basis of many tasks, such as web search and epidemic outbreak detection. In reality, networks are often multidimensional, i.e., there can exist multiple connections between any pair of nodes. In this setting, the concept of hub depends on the multiple dimensions of the network, whose interplay becomes crucial for the connectedness of a node. In this paper, we characterize multidimensional hubs. We consider the multidimensional generalization of the degree and introduce a new class of measures, that we call Dimension Relevance, aimed at analyzing the importance of different dimensions for the hubbiness of a node. We assess the meaningfulness of our measures by comparing them on real networks and null models, then we study the interplay among dimensions and their effect on node connectivity. Our findings show that: (i) multidimensional hubs do exist and their characterization yields interesting insights and (ii) it is possible to detect the most influential dimensions that cause the different hub behaviors. We demonstrate the usefulness of multidimensional analysis in three real world domains: detection of ambiguous query terms in a word-word query log network, outlier detection in a social network, and temporal analysis of behaviors in a co-authorship network.Source: Journal of computational science (Print) 2 (2011): 223–237. doi:10.1016/j.jocs.2011.05.009
DOI: 10.1016/j.jocs.2011.05.009
Metrics:
See at:
Journal of Computational Science | Journal of Computational Science | CNR ExploRA
2011
Journal article
Open Access
A classification for community discovery methods in complex networks
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: Statistical analysis and data mining (Online) 4 (2011): 512–546. doi:10.1002/sam.10133
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: Statistical analysis and data mining (Online) 4 (2011): 512–546. doi:10.1002/sam.10133
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
See at:
arXiv.org e-Print Archive | Statistical Analysis and Data Mining The ASA Data Science Journal | Statistical Analysis and Data Mining The ASA Data Science Journal | doi.org | CNR ExploRA
2010
Conference article
Open Access
As time goes by: discovering eras in evolving social networks
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus instead on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset; we illustrate how the discovered temporal clustering highlights the crucial moments when the network had profound changes in its structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: PAKSS 2010 - Advances in Knowledge Discovery and Data Mining. 14th Pacific-Asia Conference, pp. 81–90, Hyderabad, India, 21-24 June
DOI: 10.1007/978-3-642-13657-3_11
Metrics:
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus instead on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset; we illustrate how the discovered temporal clustering highlights the crucial moments when the network had profound changes in its structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: PAKSS 2010 - Advances in Knowledge Discovery and Data Mining. 14th Pacific-Asia Conference, pp. 81–90, Hyderabad, India, 21-24 June
DOI: 10.1007/978-3-642-13657-3_11
Metrics:
See at:
www.michelecoscia.com | doi.org | www.springerlink.com | CNR ExploRA
2010
Conference article
Restricted
Towards discovery of eras in social networks
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
In the last decades, much research has been devoted in topics related to Social Network Analysis. One important direction in this area is to analyze the temporal evolution of a network. So far, previous approaches analyzed this setting at both the global and the local level. In this paper, we focus on finding a way to detect temporal eras in an evolving network. We pose the basis for a general framework that aims at helping the analyst in browsing the temporal clusters both in a top-down and bottom-up way, exploring the network at any level of temporal details. We show the effectiveness of our approach to real data, by applying our proposed methodology to a co-authorship network extracted from a bibliographic dataset. Our first results are encouraging, and open the way for the definition and implementation of a general framework for discovering eras in evolving social networks.Source: Data Engineering Workshops. IEEE 26th International Conference on Data Engineering, pp. 278–281, Long Beach, USA, Febbraio 2010
DOI: 10.1109/icdew.2010.5452713
Metrics:
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
In the last decades, much research has been devoted in topics related to Social Network Analysis. One important direction in this area is to analyze the temporal evolution of a network. So far, previous approaches analyzed this setting at both the global and the local level. In this paper, we focus on finding a way to detect temporal eras in an evolving network. We pose the basis for a general framework that aims at helping the analyst in browsing the temporal clusters both in a top-down and bottom-up way, exploring the network at any level of temporal details. We show the effectiveness of our approach to real data, by applying our proposed methodology to a co-authorship network extracted from a bibliographic dataset. Our first results are encouraging, and open the way for the definition and implementation of a general framework for discovering eras in evolving social networks.Source: Data Engineering Workshops. IEEE 26th International Conference on Data Engineering, pp. 278–281, Long Beach, USA, Febbraio 2010
DOI: 10.1109/icdew.2010.5452713
Metrics:
See at:
doi.org | CNR ExploRA
2010
Conference article
Unknown
Discovering Eras in Evolving Social Networks
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
An important topic in complex network research is the temporal evolution of networks. Existing approaches aim at analyzing the evolution extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure between two temporal snapshots of the network. We devise a framework to discover and browse the eras, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks, by detecting eras in an evolving co-authorship graph; we illustrate how the discovered temporal clustering highlights the crucial moments when the network had profound changes in its structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: 18th Italian Symposium on Advanced Database Systems, pp. 78–85, Rimini, Italy, 20-23 June 2010
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
An important topic in complex network research is the temporal evolution of networks. Existing approaches aim at analyzing the evolution extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure between two temporal snapshots of the network. We devise a framework to discover and browse the eras, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks, by detecting eras in an evolving co-authorship graph; we illustrate how the discovered temporal clustering highlights the crucial moments when the network had profound changes in its structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.Source: 18th Italian Symposium on Advanced Database Systems, pp. 78–85, Rimini, Italy, 20-23 June 2010
See at: CNR ExploRA
2010
Report
Open Access
Foundations of Multidimensional Network Analysis
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Complex networks have been receiving increasing attention by the scientific community, also due to the availability of massive network data from diverse domains, and the outbreak of novel analytical paradigms, which pose relations and links among entities, or people, at the center of investigation. Networks are usually modeled by graphs. So far, network analytics has focused to the characterization and measurement of local and global properties of such graphs, such as diameter, degree distribution, centrality, connectedness - up to more sophisticated discoveries based on graph mining, aimed at finding frequent subgraph patterns and analyzing the temporal evolution of a network. However, in practice, real networks come with a rich semantics attached to relations, and nodes in a network may be connected by edges of different nature: for example, any given pair of persons may communicate with different tools (phone, email, messaging, etc), or in a social network can be linked by a different relation (being friends, colleagues, relatives, etc). A network where several possible connections (edges) exist between the same pair of entities (nodes) is called a multidimensional network. Despite the importance of this kind of network is recognized in many works, and ad-hoc analytical means have been proposed to deal with multidimensional networks of specific cases, a thorough systematic framework for multidimensional network analysis is still missing. This is precisely the aim of this paper: we develop a solid repertoire of basic concepts and analytical mechanisms, which takes into account the general structure of multidimensional networks: first, we model a multidimensional network as a multigraph, i.e., a graph where nodes can be connected by one or more labeled edges; second, we systematically develop a vast repertoire of network metrics for the graph, to characterize local and global properties of multidimensional networks. We show how popular measures like the degree of a node, the number of connected components in a graph, the shortest path, and so on, can be viewed as particular cases of more general definitions for multidimensional networks. Further, we introduce brand new metrics for multigraphs, that take into consideration the interplay among different dimension, and therefore have no counterpart in the single- dimension case. In order to demonstrate the usefulness and wide applicability of the proposed framework, we consider a large array of massive networks in diverse domains, ranging from query logs to social networks, customer networks, subgraphs and bibliographic networks, and show how in each such case the introduced metrics - both the generalization of the known ones and the brand new multidimensional metrics - reveal a surprising high analytical power and suggest novel solutions to challenging real life problems.Source: ISTI Technical reports, 2010
Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.
Complex networks have been receiving increasing attention by the scientific community, also due to the availability of massive network data from diverse domains, and the outbreak of novel analytical paradigms, which pose relations and links among entities, or people, at the center of investigation. Networks are usually modeled by graphs. So far, network analytics has focused to the characterization and measurement of local and global properties of such graphs, such as diameter, degree distribution, centrality, connectedness - up to more sophisticated discoveries based on graph mining, aimed at finding frequent subgraph patterns and analyzing the temporal evolution of a network. However, in practice, real networks come with a rich semantics attached to relations, and nodes in a network may be connected by edges of different nature: for example, any given pair of persons may communicate with different tools (phone, email, messaging, etc), or in a social network can be linked by a different relation (being friends, colleagues, relatives, etc). A network where several possible connections (edges) exist between the same pair of entities (nodes) is called a multidimensional network. Despite the importance of this kind of network is recognized in many works, and ad-hoc analytical means have been proposed to deal with multidimensional networks of specific cases, a thorough systematic framework for multidimensional network analysis is still missing. This is precisely the aim of this paper: we develop a solid repertoire of basic concepts and analytical mechanisms, which takes into account the general structure of multidimensional networks: first, we model a multidimensional network as a multigraph, i.e., a graph where nodes can be connected by one or more labeled edges; second, we systematically develop a vast repertoire of network metrics for the graph, to characterize local and global properties of multidimensional networks. We show how popular measures like the degree of a node, the number of connected components in a graph, the shortest path, and so on, can be viewed as particular cases of more general definitions for multidimensional networks. Further, we introduce brand new metrics for multigraphs, that take into consideration the interplay among different dimension, and therefore have no counterpart in the single- dimension case. In order to demonstrate the usefulness and wide applicability of the proposed framework, we consider a large array of massive networks in diverse domains, ranging from query logs to social networks, customer networks, subgraphs and bibliographic networks, and show how in each such case the introduced metrics - both the generalization of the known ones and the brand new multidimensional metrics - reveal a surprising high analytical power and suggest novel solutions to challenging real life problems.Source: ISTI Technical reports, 2010
See at:
ISTI Repository | CNR ExploRA
2009
Conference article
Open Access
Mining the temporal dimension of the information propagation
Berlingerio M., Coscia M., Giannotti F.
In the last decade, Social Network Analysis has been a field in which the effort devoted from several researchers in the Data Mining area has increased very fast. Among the possible related topics, the study of the information propagation in a network attracted the interest of many researchers, also from the industrial world. However, only a few answers to the questions "How does the information propagates over a network, why and how fast?" have been discovered so far. On the other hand, these answers are of large interest, since they help in the tasks of finding experts in a network, assessing viral marketing strategies, identifying fast or slow paths of the information inside a collaborative network. In this paper we study the problem of finding frequent patterns in a network with the help of two different techniques: TAS (Temporally Annotated Sequences) mining, aimed at extracting sequential patterns where each transition between two events is annotated with a typical transition time that emerges from input data, and Graph Mining, which is helpful for locally analyzing the nodes of the networks with their properties. Finally we show preliminary results done in the direction of mining the information propagation over a network, performed on two well known email datasets, that show the power of the combination of these two approaches.Source: Advances in Intelligent Data Analysis VIII. 8th International Symposium on Intelligent Data Analysis - IDA 2009, pp. 237–248, Lyon, France, August 31 - September 2 2009
DOI: 10.1007/978-3-642-03915-7_21
Metrics:
Berlingerio M., Coscia M., Giannotti F.
In the last decade, Social Network Analysis has been a field in which the effort devoted from several researchers in the Data Mining area has increased very fast. Among the possible related topics, the study of the information propagation in a network attracted the interest of many researchers, also from the industrial world. However, only a few answers to the questions "How does the information propagates over a network, why and how fast?" have been discovered so far. On the other hand, these answers are of large interest, since they help in the tasks of finding experts in a network, assessing viral marketing strategies, identifying fast or slow paths of the information inside a collaborative network. In this paper we study the problem of finding frequent patterns in a network with the help of two different techniques: TAS (Temporally Annotated Sequences) mining, aimed at extracting sequential patterns where each transition between two events is annotated with a typical transition time that emerges from input data, and Graph Mining, which is helpful for locally analyzing the nodes of the networks with their properties. Finally we show preliminary results done in the direction of mining the information propagation over a network, performed on two well known email datasets, that show the power of the combination of these two approaches.Source: Advances in Intelligent Data Analysis VIII. 8th International Symposium on Intelligent Data Analysis - IDA 2009, pp. 237–248, Lyon, France, August 31 - September 2 2009
DOI: 10.1007/978-3-642-03915-7_21
Metrics:
See at:
www.michelecoscia.com | doi.org | link.springer.com | CNR ExploRA
2009
Conference article
Unknown
Mining the information propagation in a network
Berlingerio M., Coscia M., Giannotti F.
In the last decade, Social Network Analysis has been a field in which the effort devoted from several researchers in the Data Mining area has increased very fast. Among the possible related topics, the study of the information propagation in a network attracted the interest of many researchers, also from the industrial world. However, only a few answers to the questionsSource: 17th Italian Symposium on Advanced Database Systems, Camogli, Genova, Italy, 21-24 June 2009
Berlingerio M., Coscia M., Giannotti F.
In the last decade, Social Network Analysis has been a field in which the effort devoted from several researchers in the Data Mining area has increased very fast. Among the possible related topics, the study of the information propagation in a network attracted the interest of many researchers, also from the industrial world. However, only a few answers to the questionsSource: 17th Italian Symposium on Advanced Database Systems, Camogli, Genova, Italy, 21-24 June 2009
See at: CNR ExploRA
2009
Conference article
Restricted
Social network analysis as knowledge discovery process: a case study on digital bibliography
Coscia M., Giannotti F., Pensa R. G.
Today Digital Bibliographies are a powerful instrument that collects a great amount of data about scientific publications. Digital Bibliographies have been used as basis of many studies focused on the knowledge extraction in database. Here we present a new methodology for mining knowledge in this field. Our approach aims to apply the potential of Social Network Analysis techniques to accomplish this task, using a network representation of bibliography data. Besides we use some Data Mining techniques applied on Social Network representations in order to enrich this new point of view and to evolve our methodology towards a comprehensive local and global Bibliography Analysis tool.Source: International Conference on Advances in Social Network Analysis and Mining, pp. 279–283, Athens, 20-22 July 2009
Coscia M., Giannotti F., Pensa R. G.
Today Digital Bibliographies are a powerful instrument that collects a great amount of data about scientific publications. Digital Bibliographies have been used as basis of many studies focused on the knowledge extraction in database. Here we present a new methodology for mining knowledge in this field. Our approach aims to apply the potential of Social Network Analysis techniques to accomplish this task, using a network representation of bibliography data. Besides we use some Data Mining techniques applied on Social Network representations in order to enrich this new point of view and to evolve our methodology towards a comprehensive local and global Bibliography Analysis tool.Source: International Conference on Advances in Social Network Analysis and Mining, pp. 279–283, Athens, 20-22 July 2009
See at:
ieeexplore.ieee.org | CNR ExploRA